package com.yubest;

/**
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。
 *
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 进阶：
 *
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *  
 *
 * 示例 1：[图片] img/0025_1.jpg
 *
 *
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 * 示例 2： [图片] img/0025_2.jpg
 *
 *
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 * 示例 3：
 *
 * 输入：head = [1,2,3,4,5], k = 1
 * 输出：[1,2,3,4,5]
 * 示例 4：
 *
 * 输入：head = [1], k = 1
 * 输出：[1]
 * 提示：
 *
 * 列表中节点的数量在范围 sz 内
 * 1 <= sz <= 5000
 * 0 <= Node.val <= 1000
 * 1 <= k <= sz
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/2 17:43
 */
public class P0025 {

    public static void main(String[] args) {
        new Solution25().reverseKGroup(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 2);

        new Solution25().reverseKGroup(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 3);

        new Solution25().reverseKGroup(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 1);

        new Solution25().reverseKGroup(new ListNode(1), 1);
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        //哨兵位
        ListNode guard = new ListNode(0, head);
        //前置节点指针
        ListNode pre = guard;
        while (true) {
            if (null == pre) {
                break;
            }
            int t = k;
            //当前需要互换的第一个节点指针
            ListNode first = pre.next;
            //当前需要互换的最后一个节点指针
            ListNode last = null;
            //当前指针
            ListNode cur = first;
            while (null != cur && t > 0) {
                last = cur;
                cur = cur.next;
                t--;
            }
            //判断元素个数是否满足k个
            if (t > 0) {
                break;
            }
            //
            pre.next = last;
            //当前操作指针
            cur = first;
            //前一个节点指针
            ListNode preNode = null;
            //下一个节点指针
            ListNode next;
            for (int i = 0; i < k; i++) {
                //如果是操作的第一个元素
                if (i == 0) {
                    //记录下一个节点位置
                    next = cur.next;
                    //当前节点指向最后节点的下一个节点位置
                    cur.next = last.next;
                    //前置指针指向下一轮需要互换的前一个节点
                    pre = cur;
                    //记录前一个节点
                    preNode = cur;
                    //当前指针移动到下一个节点
                    cur = next;
                } else {
                    //记录下一个节点
                    next = cur.next;
                    //当前指针指向前一个节点
                    cur.next = preNode;
                    //当前操作的节点标记为上一个节点的位置
                    preNode = cur;
                    //当前指针移动到下一个节点
                    cur = next;
                }
            }
        }
        return guard.next;
    }
}
